#include<iostream>
#include<vector>
#include<stack>
using namespace std;

//LeetCode 230. 二叉搜索树中第K小的元素
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct Node{
    TreeNode* node;
    int visited;
};
int kthSmallest(TreeNode* root, int k) {
    stack<Node> s;
    s.push({root, 0});
    int count = 1;
    while(!s.empty())
    {
        Node cur = s.top();
        //若该节点当前未被访问过，则先将该节点出栈,然后将右孩子先入栈，将该节点设为访问过，再将左孩子入栈
        if(cur.visited == 0)
        {
            s.pop();
            if(cur.node->right)
                s.push({cur.node->right, 0});
            s.push({cur.node, 1});
            if(cur.node->left)
                s.push({cur.node->left, 0});
        }
        else if(count==k)
            return cur.node->val;
        else{
            s.pop();
            count++;
        }
    }
}
int main()
{
    TreeNode* root = new TreeNode(5);
    TreeNode* cur = root;
    cur->left = new TreeNode(3);
    cur->right = new TreeNode(6);
    cur = cur->left;
    cur->right = new TreeNode(4);
    cur->left = new TreeNode(2);
    cur = cur->left;
    cur->left = new TreeNode(1);
    int result = kthSmallest(root, 6);
    cout << result;
    return 0;
}